package com.ruima.study.arithmetic.lookback;

import java.util.ArrayList;
import java.util.List;

/**
 * <p>
 * <p>有个盒子，从左往右的顺序排列，每个盒子中有三个不同字母，从每个盒子中取出一个字母，
 * n个盒子组成长度为的字符串，请把所有字符串罗列出来。 使用回溯算法实现（java语言）</p>
 * <p>
 * <p>Copyright (c) 2024/11/13 10:59, 科大讯飞 All Rights Reserve</p>
 *
 * @author ruima6
 * @version [V1.0]
 */
public class LookBox {
    public static void main(String[] args) {
        List<List<String>> boxes = new ArrayList<>();

        // 初始化盒子
        boxes.add(List.of("a", "b", "c"));
        boxes.add(List.of("d", "e", "f"));
        boxes.add(List.of("g", "h", "i"));

        List<String> combinations = new ArrayList<>();
        generateCombinations(boxes, 0, "", combinations);

        // 输出所有组合
        for (String combination : combinations) {
            System.out.println(combination);
        }
    }

    /**
     * 生成所有可能的组合
     *
     * @param boxes 盒子列表
     * @param index 当前处理的盒子索引
     * @param current 当前构建的字符串
     * @param combinations 存储所有组合的列表
     */
    private static void generateCombinations(List<List<String>> boxes, int index, String current, List<String> combinations) {
        // 如果已经处理完所有盒子，将当前字符串加入结果列表
        if (index == boxes.size()) {
            combinations.add(current);
            return;
        }

        // 当前盒子中的字母列表
        List<String> box = boxes.get(index);

        // 遍历当前盒子中的每个字母
        for (String letter : box) {
            // 递归处理下一个盒子
            generateCombinations(boxes, index + 1, current + letter, combinations);
        }
    }
}
